/**
 * @file 509.Fibonacci.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-16
 * 
 * @copyright Copyright (c) 2021
 * 
 * 动规 Dynamic Programming
 * 1 动规入门：斐波那契、爬楼梯、不同路径
 * 2 背包问题：0-1背包、完全背包（分割等和子集、目标和、零钱兑换）
 * 3 打家劫舍问题：I、II、III
 * 4 股票问题：I、II、III、IV、含冷冻期、含手续费
 * 5 编辑距离问题：编辑距离、不同的子序列
 * 6 子序列问题：最长递增子序列、最大子序和
 * 
 * 动规入门
 * 509.斐波那契数
 * 70.爬楼梯
 * 746.使用最小花费爬楼梯
 * 62.不同路径
 * 63.不同路径II
 * 343.整数拆分
 * 96.不同的二叉搜索树
 */

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution
{
public:
    // 509.
    int fib(int n)
    {
        // dp[n]=dp[n-1]+dp[n-2]
        if (n == 0 || n == 1) {
            return n;
        }
        int dp0 = 0, dp1 = 1;
        int dpn;
        for (int i = 2; i <= n; ++i) {
            dpn = dp0 + dp1;
            dp0 = dp1;
            dp1 = dpn;
        }
        return dpn;
    }
    // 70.
    int climbStairs(int n)
    {
        if (n == 1 || n == 2) {
            return n;
        }
        int dp0 = 1, dp1 = 2;
        int dpn;
        for (int i = 3; i <= n; ++i) {
            dpn = dp0 + dp1;
            dp0 = dp1;
            dp1 = dpn;
        }
        return dpn;
    }
    // 746.
    int minCostClimbingStairs(vector<int> &cost)
    {
        /**
         * dp[i] 到达第i个台阶所需的最小花费
         * dp[i]=min(dp[i-1],dp[i-2])+cost[i]
         * return dp[i-1]
         * dp[0]=cost[0],dp[1]=cost[1]
         */
        int n = cost.size();
        vector<int> dp(n, 0);
        dp[0] = cost[0], dp[1] = cost[1];
        for (int i = 2; i < n; ++i) {
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        return min(dp[n - 2], dp[n - 1]);
    }
    // 62.
    int uniquePaths(int m, int n)
    {
        /***
         * dp[i][j] 到达(i,j)的路径总数
         * dp[i][j]=dp[i-1][j]+dp[i][j-1]
         * return dp[m-1][n-1]
         * */
#if 0
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
#endif
        /***
         * dp[i][j]=dp[i-1][j]+dp[i][j-1]
         * 状态压缩：压缩i维度
         * dp[j]=dp[j]+dp[j-1]
         * **/
        vector<int> dp(n, 1);
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
    // 63. 加障碍物
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i) {
            // 发现障碍物，其后均为0
            if (obstacleGrid[i][0] == 1) {
                break;
            }
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            if (obstacleGrid[0][j] == 1) {
                break;
            }
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
    // 343.将一个整数拆成n个数之和，使其乘积最大
    int integerBreak(int n)
    {
        /***
         * 2 <= n <= 58
         * 每个数可以选择拆成n个或者就拆成2个
         * dp[i]=max(dp[i-j]*j, (i-j)*j) j从1开始枚举
         * **/
        vector<int> dp(n + 1, 0);
        dp[2] = 1;
        for (int i = 3; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                // 这里枚举j，取枚举过程中的最大值，所以带上dp[i]
                dp[i] = max(max(dp[i - j] * j, (i - j) * j), dp[i]);
            }
        }
        return dp[n];
    }
    // 96.
    int numTrees(int n)
    {
        /***
         * 可以递归，那就想想斐波那契，用动规来做记忆化搜索
         * dp[i] 1到i为节点组成的BST个数
         * 枚举j，对其求和，1 <= j <= i
         * 以j为头结点，左子树个数dp[j-1]
         * 以j为头结点，右子树个数dp[i-j]
         * **/
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};

Solution solve = Solution();

void test509()
{
    for (int i = 0; i <= 10; ++i) {
        cout << solve.fib(i) << endl;
    }
}
void test70()
{
    for (int i = 1; i <= 10; ++i) {
        cout << solve.climbStairs(i) << endl;
    }
}
void test746()
{
    vector<int> cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
    cout << solve.minCostClimbingStairs(cost) << endl;
}
void test62()
{
    cout << solve.uniquePaths(3, 7) << endl;
}
void test63()
{
    vector<vector<int>> obs = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
    cout << solve.uniquePathsWithObstacles(obs) << endl;
}
void test343()
{
    cout << solve.integerBreak(10) << endl;
}
void test96()
{
    cout << solve.numTrees(3) << endl;
}
int main()
{
    // test509();
    // test70();
    // test746();
    // test62();
    // test63();
    // test343();
    test96();
    return 0;
}